﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace Dijkstra_Belman_Ford
{
    public class Graf
    {
        public int[,] waga;
        private int[] d,p,w,b;
        public int liczbaWierzcholkow;
        bool[] QS;
        const int inf = 300000;
        public Stopwatch sw1 = new Stopwatch();
        public Stopwatch sw2 = new Stopwatch();

        public Graf(int v=0)
        {
            liczbaWierzcholkow = v;
            waga = new int[v,v];
            for (int i = 0; i < v; i++)
                for(int j= 0; j < v; j++)
                waga[i,j] = 0;
        }

        public void Add(int v1=0, int v2=0,int w=0)
        {
            waga[v1, v2] = w;
        }

        public int CountEdges(int v = 0)
        {
            int count = 0;
            for (int i=0;i<v;i++)
                for (int j=0;j<v;j++)
                    if(waga[i,j] !=0)
                        count++;
            return count;
        }

        public string ShowGraph(int v = 0)
        {
            string s=null;
            for (int i = 0; i < v; i++)
                for (int j = 0; j < v; j++)
                    if(j<v-1)
                        s += waga[i, j].ToString() +' ' +'|'+' ';
                    else
                        s += waga[i, j].ToString() +' '+'|'+' '+'\n';
            return s;
        }

        public void Bellman_Ford(int v=0)
        {
            v = liczbaWierzcholkow;
            sw1.Start();
            w = new int[v];
            b = new int[v];
            for (int i = 1; i < v; i++)
            {
                w[i] = inf;
                b[i] = inf;
            }
            w[0] = 0;
            for (int k = 1; k < v - 1; k++)
            {
                for (int i = 1; i < v; i++)
                    for (int j = 0; j < v; j++)
                    {
                        if (waga[i, j] != 0)
                        {
                            if (w[j] + waga[j, i] < w[i])
                            {
                                w[i] = w[j] + waga[j, i];
                                b[i] = j;
                            }
                        }
                    }
            }
            sw1.Stop();
        }

        public void Dijkstry(int v = 0)
        {
            v = liczbaWierzcholkow;
            sw2.Start();
            int u;
            d = new int[v];
            p = new int[v];
            QS = new bool[v];
            for (int i = 0; i < v; i++)
            {
                d[i] = inf;
                p[i] = inf;
                QS[i] = false;
            }

            d[0] = 0;

            for (int i = 0; i < v; i++)
            {
                u = -1;
                for (int j = 0; j < v; j++)
                    if (!QS[j] && ((u == -1) || (d[j] < d[u])))
                        u = j;
                QS[u] = true;
                for (int j = 0; j < v; j++)
                {
                    if (waga[u, j] != 0)
                        if (!QS[j] && d[u] + waga[u, j] < d[j])
                        {
                            d[j] = d[u] + waga[u, j];
                            p[j] = u;
                        }
                }
            }
            sw2.Stop();
        }

        public string ShowBellmanFord(int v = 0)
        {
            string s = null;
            int j,k = 0;
            for (int i = 1; i < v; i++)
            {
                j = i;
                s += (i + 1).ToString() + "->";
                while (j != 0 && b[j] != inf)
                {
                    j = b[j];
                    if (j == 0)
                        s += (j + 1).ToString();
                    else
                        s += (j + 1).ToString() + "->";
                }

                s += " koszt: " + w[i].ToString() + "\n";
                if(w[i] !=inf)
                    k += w[i];
            }

            s += "\n" + "koszt calkowity: " + k.ToString();
            return s;
        }

        public string ShowDijkstry(int v = 0)
        {
            string s = null;
            int j,k = 0;
            for (int i = 1; i < v; i++)
            {
                j=i;
                s += (i+1).ToString()+"->";
                while (j != 0 && p[j] != inf)
                {
                    j = p[j];
                    if (j == 0)
                        s += (j + 1).ToString();
                    else
                        s +=(j+1).ToString()+"->";
                }
                s+=" koszt: "+d[i].ToString()+"\n";
                if (d[i] != inf)
                    k += d[i];
            }

            s += "\n" + "koszt calkowity: " + k.ToString();
            return s;
        }

        public string ShowTimeBellmanFord()
        {
            string time=null; 
            time += "Czas operacji: " + sw1.ElapsedMilliseconds.ToString() +" ms";
            return time;
        }

        public double ShowTimeBF()
        {
            double time = sw1.ElapsedMilliseconds;
            return time;
        }

        public string ShowTimeDijkstry()
        {
            string time = null;
            time +="Czas operacji: " + sw2.ElapsedMilliseconds.ToString() +" ms";
            return time;
        }

        public double ShowTimeD()
        {
            double time = sw2.ElapsedMilliseconds;
            return time;
        }
    }
}
